home *** CD-ROM | disk | FTP | other *** search
/ Whiteline: Alpha / Whiteline Alpha.iso / progtool / modula2 / hk_lib / def_mod / longsets.def < prev    next >
Encoding:
Modula Definition  |  1994-09-22  |  12.3 KB  |  242 lines
  1. DEFINITION MODULE  LongSets;
  2.  
  3. (*****************************************************************************)
  4. (* Die vorliegende MODULA-Implementation stellt nur Mengen mit maximal 16    *)
  5. (* Elementen zur Verfuegung. Da sich mancherlei Dinge sehr elegant mit Mengen*)
  6. (* und den auf ihnen definierten Operationen loesen lassen, stellt dieses Mo-*)
  7. (* dul Mengenoperationen zur Verfuegung, die mit einem hier zu definierenden *)
  8. (* Mengentyp arbeiten.                                                       *)
  9. (*                                                                           *)
  10. (* Die Menge selber ist ein ARRAY von BITSETs; je nach Anwendung muss nun    *)
  11. (* noch der Typ der Mengenelemente angegeben werden ( SetElement = ... ).    *)
  12. (* Das kann durch Aufzaehlung geschehen - SetElement = ( e1, e2, e3 ... en ) *)
  13. (* oder durch Angabe eines Standardtyps, hier ist aber nur CHAR sinnvoll.    *)
  14. (* Wenn ein Unterbereichstyp angegeben werden soll, muss die untere Grenze   *)
  15. (* mit Null beginnen - SetElement = [0..1023].                               *)
  16. (*                                                                           *)
  17. (* Ist der Typ festgelegt, muessen Definitios- und Implementationsmodul neu  *)
  18. (* uebersetzt werden; eine Aenderung der Prozeduren ist nicht notwendig      *)
  19. (*                                                                           *)
  20. (* Bei den Hinweisen auf die aequivalenten logischen Operationen ist zu be-  *)
  21. (* achten, dass bitweise Operationen gemeint sind.                           *)
  22. (*___________________________________________________________________________*)
  23. (*   10-Jan-89 , Holger Kleinschmidt                                         *)
  24. (*****************************************************************************)
  25.  
  26. FROM  SYSTEM  IMPORT  (* PROC *) VAL;
  27.  
  28. (*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
  29.  
  30.   TYPE
  31.         SetElement   = CHAR;
  32.  
  33.   (* Als 'SetElement' kann ein beliebiger Aufzaehlungstyp,
  34.    * oder ein nichtstrukturierter Typ  wie CHAR oder
  35.    * CARDINAL stehen. Bei Standardtypen wie CARDINAL
  36.    * ist allerdings Vorsicht geboten: die haben meistens
  37.    * eine sehr grosse Anzahl Elemente...
  38.    *)
  39.  
  40.  
  41.   CONST
  42.         ElementsInBITSET = 16;
  43.         ElementsInSet    = VAL( CARDINAL, MAX(SetElement) ) + 1;
  44.  
  45.         NoOfBITSETs      = (( ElementsInSet - 1 ) DIV ElementsInBITSET ) + 1;
  46.         LastElements     = (( ElementsInSet - 1 ) MOD ElementsInBITSET ) + 1;
  47.  
  48.         (* "LastElements" enthaelt die Anzahl der belegten Bits
  49.          * in der Letzten BITSET; Ist "ElementsInSet" ein Vielfaches
  50.          * von 16, so ist "LastElements" = 16, wird nur ein Element
  51.          * in der letzten BITSET benutzt, so ist "LastElements" = 1
  52.          *)
  53.  
  54.  
  55.   TYPE
  56.         Set              = ARRAY [ 0..NoOfBITSETs - 1 ] OF  BITSET;
  57.  
  58. (*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
  59.  
  60.  
  61.   PROCEDURE NoElements  ((* -- /AUS *) VAR  menge : Set );
  62.  
  63.   PROCEDURE AllElements ((* -- /AUS *) VAR  menge : Set );
  64.  
  65.  (*-------------------------------------------------------------------------
  66.   | Loescht, bzw. setzt alle Elemente von <menge>.                          |
  67.    -------------------------------------------------------------------------*)
  68.  
  69.  
  70.   PROCEDURE IsEmptySet ((* EIN/ -- *) menge : Set ): BOOLEAN;
  71.  
  72.   PROCEDURE IsFullSet  ((* EIN/ -- *) menge : Set ): BOOLEAN;
  73.  
  74.  (*-------------------------------------------------------------------------
  75.   | Prueft, ob <menge> leer ist,bzw. alle moeglichen Elemente enthalten sind|
  76.    -------------------------------------------------------------------------*)
  77.  
  78.  
  79.   PROCEDURE Complement ((* EIN/ -- *)     menge : Set;
  80.                         (* -- /AUS *) VAR compl : Set  );
  81.  
  82.  (*-------------------------------------------------------------------------
  83.   | <compl> enthaelt die Komplemaentaermenge von <menge>, d.h. in <compl>   |
  84.   | sind genau die Elemente enthalten, die in <menge> nicht enthalten sind. |
  85.   |                                                                         |
  86.   | Dies ist die logische Operation:   <compl> := NOT <menge>               |
  87.    -------------------------------------------------------------------------*)
  88.  
  89.  
  90.   PROCEDURE Card ((* EIN/ -- *) menge : Set ): CARDINAL;
  91.  
  92.  (*-------------------------------------------------------------------------
  93.   | Liefert die Kardinalitaet, d.h. die Anzahl der Elemente von <menge>.    |
  94.    -------------------------------------------------------------------------*)
  95.  
  96.  
  97.   PROCEDURE IsElement ((* EIN/ -- *) elem  : SetElement;
  98.                        (* EIN/ -- *) menge : Set        ): BOOLEAN;
  99.  
  100.  (*-------------------------------------------------------------------------
  101.   | Testet, ob das Element <elem> in der Menge <menge> enthalten ist.       |
  102.    -------------------------------------------------------------------------*)
  103.  
  104.  
  105.   PROCEDURE Include ((* EIN/ -- *)     elem  : SetElement;
  106.                      (* EIN/AUS *) VAR menge : Set        );
  107.  
  108.   PROCEDURE Exclude ((* EIN/ -- *)     elem  : SetElement;
  109.                      (* EIN/AUS *) VAR menge : Set        );
  110.  
  111.  (*-------------------------------------------------------------------------
  112.   | Fuegt das Element <elem> der Menge <menge> hinzu, bzw. entfernt es.     |
  113.   |  - Falls <elem> bei Aufruf von "Include" bereits in der Menge enthalten |
  114.   |    ist, wird <menge> nicht veraendert                                   |
  115.   |  - Falls <elem> bei Aufruf von "Exclude" nicht in der Menge enthalten   |
  116.   |    ist, wird <menge> nicht veraendert                                   |
  117.    -------------------------------------------------------------------------*)
  118.  
  119.   PROCEDURE IncludeRange ((* EIN/ -- *)     von,
  120.                           (* EIN/ -- *)     bis   : SetElement;
  121.                           (* EIN/AUS *) VAR menge : Set        );
  122.  
  123.   PROCEDURE ExcludeRange ((* EIN/ -- *)     von,
  124.                           (* EIN/ -- *)     bis   : SetElement;
  125.                           (* EIN/AUS *) VAR menge : Set        );
  126.  
  127.  (*-------------------------------------------------------------------------
  128.   | Der Bereich von Elementen zwischen <von> und <bis> ( einschliesslich )  |
  129.   | wird <menge> hinzugefuegt, bzw. aus <menge> entfernt.                   |
  130.   |  - Liegt <bis> vor <vor>, passiert nichts.                              |
  131.   |  - Liegt <bis> ausserhalb von <menge>, werden nur die Elemente bis zum  |
  132.   |    Mengenende beruecksichtigt.                                          |
  133.    -------------------------------------------------------------------------*)
  134.  
  135.  
  136.   PROCEDURE Union ((* EIN/ -- *)     menge1,
  137.                    (* EIN/ -- *)     menge2 : Set;
  138.                    (* -- /AUS *) VAR verein : Set  );
  139.  
  140.  (*-------------------------------------------------------------------------
  141.   | Bildet die Vereinigungsmenge. D.h. <verein> enthaelt alle Elemente von  |
  142.   | <menge1> und <menge2>. In beiden Mengen auftretende Elemente sind in    |
  143.   | <verein> nur einmal enthalten.                                          |
  144.   |                                                                         |
  145.   | Dies ist die logische Operation:   <verein> := <menge1> OR <menge2>     |
  146.    -------------------------------------------------------------------------*)
  147.  
  148.  
  149.   PROCEDURE Intersection ((* EIN/ -- *)     menge1,
  150.                           (* EIN/ -- *)     menge2  : Set;
  151.                           (* -- /AUS *) VAR schnitt : Set  );
  152.  
  153.  (*-------------------------------------------------------------------------
  154.   | Bildet die Schnittmenge. D.h. <schnitt> enthaelt die Elemente, die so-  |
  155.   | wohl in <menge1> als auch in <menge2> enthalten sind.                   |
  156.   |                                                                         |
  157.   | Dies ist die logische Operation:   <schnitt> := <menge1> AND <menge2>   |
  158.    -------------------------------------------------------------------------*)
  159.  
  160.  
  161.   PROCEDURE Difference ((* EIN/ -- *)     menge1,
  162.                         (* EIN/ -- *)     menge2 : Set;
  163.                         (* -- /AUS *) VAR diff   : Set  );
  164.  
  165.  (*-------------------------------------------------------------------------
  166.   | Bildet die Differenzmenge. D.h. in <diff> sind alle Elemente von        |
  167.   | <menge1> enthalten, die nicht auch in <menge2> enthalten sind.          |
  168.   |                                                                         |
  169.   | Dies ist die logische Operation:   <diff> := <menge1> AND NOT <menge2>  |
  170.    -------------------------------------------------------------------------*)
  171.  
  172.  
  173.   PROCEDURE SymmetricDiff ((* EIN/ -- *)     menge1,
  174.                            (* EIN/ -- *)     menge2  : Set;
  175.                            (* -- /AUS *) VAR symdiff : Set  );
  176.  
  177.  (*-------------------------------------------------------------------------
  178.   | Bildet die symmetrische Differenz. D.h. in <symdiff> sind alle Elemente |
  179.   | enthalten, die entweder in <menge1> oder in <menge2> enthalten sind,    |
  180.   | nicht aber in beiden. Die symmetrische Differenz ist die Differenzmenge |
  181.   | von Vereinigungs - und Schnittmenge.                                    |
  182.   |                                                                         |
  183.   | Dies ist die logische Operation:   <symdiff> := <menge1> XOR <menge2>   |
  184.    -------------------------------------------------------------------------*)
  185.  
  186.  
  187.   PROCEDURE Equal ((* EIN/ -- *) menge1,
  188.                    (* EIN/ -- *) menge2 : Set ): BOOLEAN;
  189.  
  190.  (*-------------------------------------------------------------------------
  191.   | Testet, ob <menge1> und <menge2> gleich sind.                           |
  192.    -------------------------------------------------------------------------*)
  193.  
  194.  
  195.   PROCEDURE IsSubset       ((* EIN/ -- *) menge1,
  196.                             (* EIN/ -- *) menge2 : Set ): BOOLEAN;
  197.  
  198.   PROCEDURE IsProperSubset ((* EIN/ -- *) menge1,
  199.                             (* EIN/ -- *) menge2 : Set ): BOOLEAN;
  200.  
  201.  (*-------------------------------------------------------------------------
  202.   | Testet, ob <menge1> eine ( echte ) Teilmenge von <menge2> ist, d.h. ob  |
  203.   | alle Elemente von <menge1> auch in <menge2> enthalten sind.             |
  204.   | "IsProperSubset" verlangt zusaetzlich noch, dass die beiden Mengen nicht|
  205.   | gleich sind.                                                            |
  206.   |                                                                         |
  207.   | Dies ist die logische Operation:     <menge1> AND NOT <menge2> = 0      |
  208.    -------------------------------------------------------------------------*)
  209.  
  210.  
  211.   PROCEDURE IsSuperset       ((* EIN/ -- *) menge1,
  212.                               (* EIN/ -- *) menge2 : Set ): BOOLEAN;
  213.  
  214.   PROCEDURE IsProperSuperset ((* EIN/ -- *) menge1,
  215.                               (* EIN/ -- *) menge2 : Set ): BOOLEAN;
  216.  
  217.  (*-------------------------------------------------------------------------
  218.   | Testet, ob <menge1> eine ( echte ) Obermenge von <menge2> ist, d.h. ob  |
  219.   | alle Elemente von <menge2> auch in <menge1> enthalten sind.             |
  220.   | "IsProperSuperset" verlangt zusaetzlich noch, dass die beiden Mengen    |
  221.   | nicht gleich sind.                                                      |
  222.   |                                                                         |
  223.   | Dies ist die logische Operation:     <menge2> AND NOT <menge1> = 0      |
  224.    -------------------------------------------------------------------------*)
  225.  
  226.  
  227.   PROCEDURE WriteSet ((* EIN/ -- *) menge : Set );
  228.  
  229.  (*-------------------------------------------------------------------------
  230.   | Ist der Versuch, eine Menge auszugeben.                                 |
  231.   | Pro Zeile werden vier BITSETs ausgegeben, jeweils getrennt durch '|'.   |
  232.   | Fuer ein vorhandenes Element wird ein '1', fuer ein nicht vorhandenes   |
  233.   | Element '0' geschrieben. Es werden genau soviele Elemente dargestellt,  |
  234.   | wie maximal in "Set" vorhanden sein koennen. Evtl. zusaetzliche Bits in |
  235.   | der letzten BITSET werden nicht dargestellt.                            |
  236.   | Die Position der Elemente nimmt von links nach rechts und von oben nach |
  237.   | unten zu.                                                               |
  238.   | Die Prozedur ist eigentlich nur zu Testzwecken gedacht.                 |
  239.    -------------------------------------------------------------------------*)
  240.  
  241. END  LongSets.
  242.